Finite element analysis is a widely used computer-aided design tool for solving engineering problems governed by partial differential equations. Such problems analyze the effects on a body of heat transfer flow, stress, vibration, fluid flow etc. Finite element analysis is particularly important when the shape of a body to be modelled is relatively complex, since the differential equations for such applications become increasingly difficult to solve or even to approximate.
An initial stage of a finite element analysis involves the creation of a mesh of points that are interconnected and become vertices of finite elements, both on the surface of the body and, in 3-D, in its interior. Accurate finite element analysis requires that a point placement method be employed which yields a mesh that satisfies at least four criteria: (1) the overall point or vertex density is able to be specified; (2) the density of vertices should increase in critical regions, (i.e., those which have small features and concave corners); (3) "skinny" finite elements are to be avoided; and (4) a mesh derived from a set of vertices should be able to be refined in certain areas by the user or the finite element analysis solving algorithm.
In the prior art, the generation of a 3-D mesh suitable for finite element analysis has been one of the most time consuming steps in using the computer to analyze a complex engineering problem. Most previous work on 3-dimensional point placement has been heuristic in nature. Many approaches have required significant manual interaction between the user and the point placement map and subsequent manual corrections of the output.
In the scientific literature, considerable attention has been paid to methods for generating meshes for use in finite element analysis. Three papers appearing in the International Journal for Numerical Methods and Engineering consider various applications of Delaunay triangulation and the generation of a mesh therefor. Those papers are as follows: Cavendish et al., Vol. 21, pp. 329-347, (1985); Frey, Vol. 24, pp. 2183-2200 (1987); and Schroeder et al., Vol. 26, pp. 2503-2515 (1988). Each of the aforementioned articles employs a teaching of Delaunay to achieve planar triangulation and three-dimensional tetrahedrization. A tetrahedral mesh is said to be a "Delaunay tetrahedrization" if the following is true for each tetrahedron in the mesh: the sphere defined by the four vertices of the tetrahedron, called its circumsphere, contains no mesh vertices in its interior. Vertices on the circumsphere's boundary are permitted.
The same property applies to two-dimensional surfaces. Given a three vertex triangulation if and only if a circle defined by the three vertices contains no other vertices in its interior, is the triangulation defined as a Delaunay triangulation. Cavendish et al. implements such a triangulation by rejecting from the set of all possible triangles which might be formed, those with non-empty associated circles. Those triangles not rejected, form the Delaunay triangulation. Frey employs a similar triangulation scheme and further teaches a method for selective refinement of an initial triangulation. Grading of the mesh is controlled by a node spacing function wherein a respective node is inserted and its spacing from adjacent nodes is evaluated. Each new prospective node is also tested to see if its insertion would lead to a Delaunay triangulation with an acceptable degree of spacing at the new node.
Schroeder et al. apply those teachings to three-dimensional surfaces.
Further references which discuss methods for mesh generation can be found in the following: Yerry et al., International Journal for Numerical Methods and Engineering, Vol. 20, pp. 1965-1990 (1984); Cendes et al., IEEE Transactions on Magnetics, Vol. Mag-19, No. 6, pp. 2551-2554 (1983); Field, "Second International Symposium on Computational Geometry", pp. 246-259 (1986); Schrieber, IBM Technical Disclosure Bulletin, Vol. 18, No. 4, pp. 1163-1176 (1975) and Koyamada, IBM Technical Disclosure Bulletin, Vol. 32, No. 1, pp. 340-342 (1989).
In U.S. Pat. No. 4,912,664 to Weiss et al., a 2-D approach to generating a mesh using Delaunay triangulation is described. Weiss et al. employ an expert-system based point placement algorithm and an element of "goodness" criterion for point selection. Weiss et al. teach that points are placed in a 2-D mesh until all resulting elements meet a goodness criteria.
In U.S. Pat. No. 4,933,889 to Meshkat et al., a further 2-D approach for generating a mesh using symmetric axis decomposition is disclosed. The method taught therein is not point based, but does employ the symmetric axis of a body to enable finite elements to be calculated.
Mesh generation has also been employed to enable the rendering of three-dimensional displays of various bodies. Description of representative systems for enabling such displays may be found in the following patents: Falk, U.S. Pat. No. 4,888,713; Reilly, U.S. Pat. No. 4,930,092 and Draney, U.S. Pat. No. 4,829,446.
It is an object of this invention to provide an improved point placement method for use in a three-dimensional, automatic mesh generation algorithm.
It is another object of this invention to provide an automated point placement method wherein mesh grading and mesh refinement are automatically controlled.
It is still another object of this invention to provide a point placement method wherein point density is controlled automatically.
It is still a further object of this invention to provide an improved point placement method which prevents badly shaped mesh elements from appearing in the resulting mesh.